package com.fsy.algorithm;


/**
 * Created by shuangyu.feng on 2017/7/11.
 */
public class DpArray
{
    private static final int[] array = new int[]{111112,-1133312,-12,21,21,3,-7,21,-55,-121,124,-89,99,-123,111,12,80,-12,21,21,3,-7,21,-55,-121,124,-89,99,-199,111,12,80,-12,21,21,3,-7,21,-55,-121,124,-89,99,-183,111,12,80,-12,21,21,3,-7,21,-55,-121,124,-89,99,-123,111};

    private static Object[][] arrayC = new Object[array.length][2];
    private static int eleIndex = 0;
    public static void main(String[] args){
//        Long startDate = System.currentTimeMillis();
//        rangeArray();
//
//        rangeArrayC();
//        Long endDate = System.currentTimeMillis();
//        for(int i = 0 ; i<= eleIndex;i++){
//            Object[] node = arrayC[i];
//            Integer[] key = (Integer[]) node[0];
//            for(int j = 0; j < key.length;j++){
//                if(null == key[j]) break;
//                System.out.print(key[j] + " ");
//            }
//            System.out.print(":>>>>>>>>>"+node[1]);
//            System.out.println();
//        }
//
//        System.out.println("run time :" + (startDate-endDate));
        getMax(array);
    }

    private static void rangeArrayC() {
        int oldIndex = eleIndex;
        for(int i = eleIndex; i >= 2;){
            Object[] node1 = arrayC[i];
            Integer value1 = Integer.valueOf(node1[1].toString());
            if(value1 < 0){
                i--;
                break;
            }

            Object[] node2 = arrayC[i-1];
            Integer value2 = Integer.valueOf(node2[1].toString());

            Object[] node3 = arrayC[i-2];
            Integer value3 = Integer.valueOf(node3[1].toString());

            if(value1 + value2 >= 0
                    && value2 +value3 >=0){
                node3[1]=value1+value2+value3;
                Integer[] keys = (Integer[]) node3[0];
                addArrayIndex(keys,node1);
                addArrayIndex(keys,node2);
                arrayMove(i-1,2);
                break;
            }

            i = i - 2;
        }

        if(oldIndex != eleIndex){
            rangeArrayC();
        }
    }

    private static void arrayMove(int index,int step){
        for(int i = index ; i < arrayC.length;i++){
            if(i+2<arrayC.length){
                arrayC[i] = arrayC[i+step];
            }else{
                arrayC[i] = null;
            }
        }
    }

    private static void addArrayIndex(Integer[] keys, Object[] node) {
        int keyIndex = 0;
        for(Integer key : keys){
            if(null != key){
                keyIndex++;
            }else{
                break;
            }
        }

        Integer[] Oldkeys = (Integer[]) node[0];
        for(Integer key : Oldkeys){
            if(null != key){
                keys[keyIndex] = key;
                keyIndex++;
            }else{
                break;
            }
        }
        node = null;
        eleIndex--;
    }

    private static void rangeArray() {
        for(int i = 0; i < array.length ;i++){
            Object[] node = arrayC[eleIndex];
            if(node[0] == null){
                resetArrayC(node);
                putArrayEle(node,i,array[i]);
            }else{
                Integer value = Integer.valueOf(node[1].toString());
                if(comparedType(value,array[i])){
                    putArrayEle(node,i,array[i]);
                }else{
                    eleIndex++;
                    node = arrayC[eleIndex];
                    resetArrayC(node);
                    putArrayEle(node,i,array[i]);
                }
            }

        }
    }

    private static void putArrayEle(Object[] node,int index, Integer num) {
        Integer[] key = (Integer[]) node[0];
        for(int i = 0;i<key.length;i++){
            if(key[i] == null){
                key[i] = index;
                break;
            }
        }
        Integer value = Integer.valueOf(node[1].toString());
        node[1] =value + num;
    }

    private static void resetArrayC(Object[] integers) {
        integers[0] = new Integer[array.length];
        integers[1] = 0;
    }


    private static boolean comparedType(Integer ele1,Integer ele2){
        if(ele1 >= 0 && ele2 >=0)return true;
        if(ele1 < 0 && ele2 <0)return true;
        return false;
    }

    public static void getMax(int[] num){
        int start=0;
        int end=0;
        int max=0;
        int temp=0;
        int ts=0;
        int ends=0;
        for(int i=0;i<num.length;i++){
            temp=temp+num[i];
            if(temp<0){
                ts=i+1;
                ends=i+1;
                temp=0;
            }else{
                if(temp>max){
                    start=ts;
                    end=ends;
                    max=temp;
                }
            }
        }
        System.out.println("maxsum="+max+",start:"+start+",end="+end);
    }
}
